﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StrategyAndSort
{
    /// <summary>
    /// 快速排序
    /// </summary>
    class QuickSort : ISortStrategy
    {
        public void Sort<T>(IList<T> array,int keyNum = 0) where T : IComparable
        {
            QuickSortEnter(array, 0, array.Count-1);
        }

        private void QuickSortEnter<T>(IList<T> array ,int left ,int right) where T:IComparable
        {
            if (left < right)
            {
                int pivot = Parttion<T>(array, left, right);
                //因为经过一趟快排之后，pivot的元素已经有序，所以pivot不用再参与排序
                QuickSortEnter(array, left, pivot - 1);
                QuickSortEnter(array, pivot + 1, right);
            }
        }

        private int Parttion<T>(IList<T> array,int left ,int right) where T:IComparable
        {
            T temp = array[left];
            while (right>left)
            {
                //元素相等的情况也要处理
                while (right > left && array[right].CompareTo(temp) >=0) right--;
                array[left] = array[right];
                while (right > left && array[left].CompareTo(temp) <= 0) left++;
                array[right] = array[left];
            }
            array[left] = temp;
            return left;
        }


    }
}
